package org.gzc.linklist;

/**
 * @Description:
 * @Author: guozongchao
 * @Date: 2020/8/3 21:24
 */
public class CircleLinkList {

    public static void main(String[] args) {
        //测试数据
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        Node n5 = new Node(5);
        Node n6 = new Node(6);
        Node n7 = new Node(7);

        //创建单链表
        n1.setNext(n2);
        n2.setNext(n3);
        n3.setNext(n4);

        n5.setNext(n7);
        n7.setNext(n6);

        //将单链表n1转成循环链表
        transferToCircleLinkList(n1);
        //遍历，为了看循环效果，从不同的结点开始遍历
        System.out.println("循环链表n1:");
        display(n1);
        display(n2);
        display(n3);

        //添加n5单链表到循环链表n1
        System.out.println("\n添加n5单链表到循环链表n1");
        add(n1, n5);
        display(n1);
        display(n5);

        //移除指定结点
        System.out.println("\n移除指定结点6");
        remove(n1, 6);
        display(n1);
    }

    //将单链表变成一个循环链表
    public static void transferToCircleLinkList(Node node) {
        if (node == null) {
            return;
        }
        Node temp=node;
        while (temp.getNext() != null) {
            temp=temp.getNext();
        }
        temp.setNext(node);
    }

    //遍历循环链表
    public static void display(Node node) {
        Node current=node;
        while (true) {
            System.out.print(current + "--->");
            if(current.getNext() == node){
                break;
            }
            current=current.getNext();
        }
        System.out.println();
    }

    //添加单个结点或者单链表到指定循环链表中
    public static void add(Node circleNode, Node newNode) {
        Node curr=circleNode;
        while (curr.getNext() != circleNode) {
            curr=curr.getNext();
        }
        curr.setNext(newNode);
        curr=newNode;
        while (curr.getNext() != null) {
            curr = curr.getNext();
        }
        curr.setNext(circleNode);
    }

    //移除指定值结点
    public static void remove(Node node,int val) {
        Node pre=node;
        Node start = node.getNext();
        Node curr=start;
        boolean found=false;
        while (true) {
            if (curr.getVal() == val) {
                found=true;
                break;
            }
            if (curr.getNext() == start) {
                break;
            }
            pre=curr;
            curr=curr.getNext();
        }
        if(!found){
            throw new RuntimeException("Not Found!");
        }
        pre.setNext(curr.getNext());
    }

}



class Node {
    private int val;
    private Node pre;
    private Node next;

    public Node(int val) {
        this.val=val;
    }

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public Node getPre() {
        return pre;
    }

    public void setPre(Node pre) {
        this.pre = pre;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                '}';
    }
}